package written_examination_questions;

import java.util.HashMap;

public class Demo20251107 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // nums1, nums2, 合并数组的的最后一位
        int i = m - 1, j = n - 1, k = m + n - 1;
        // 从后往前遍历合并
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        // 当nums1遍历完但nums2没有遍历完，直接将nums2剩余的元素复制到nums1前边
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

/**
 * LRU 缓存
 */
class LRUCache {
    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(-1, -1); // 虚拟节点
        this.tail = new Node(-1, -1); // 虚拟节点
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value; // 值覆盖
            removeNode(node);
            addToHead(node);
        } else {
            // 已经满了，删除最不常用的key value
            if (size >= capacity) {
                Node last = tail.prev;
                removeNode(last);
                map.remove(last.key);
                size--;
            }
            // 如果没满
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
        }
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

// 定义节点
class Node {
    int key;
    int value;
    Node prev;
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
